package topics;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @program: common_parents
 * @description: 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 方案一：使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
 * <p>
 * 方案二：不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置
 * @author: jatej
 * @create: 2021-06-08 10:31
 **/
public class FindMedianSortedArrays {
    public static void main(String[] args) {
//        输入：nums1 = [1,3], nums2 = [2]
//        输出：2.00000
//        解释：合并数组 = [1,2,3] ，中位数 2

//        输入：nums1 = [1,2], nums2 = [3,4]
//        输出：2.50000
//        解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

//        输入：nums1 = [0,0], nums2 = [0,0]
//        输出：0.00000

//        输入：nums1 = [], nums2 = [1]
//        输出：1.00000

//        输入：nums1 = [2], nums2 = []
//        输出：2.00000

//        提示：
//        nums1.length == m
//        nums2.length == n
//        0 <= m <= 1000
//        0 <= n <= 1000
//        1 <= m + n <= 2000
//         -106 <= nums1[i], nums2[i] <= 106

        int[] nums1, nums2;
        System.out.println("测试一");
        nums1 = new int[]{1, 3};
        nums2 = new int[]{2};
        System.out.println(findMedianSortedArrays(nums1, nums2));//输出：2.00000
        System.out.println("测试二");
        nums1 = new int[]{1, 2};
        nums2 = new int[]{3, 4};
        System.out.println(findMedianSortedArrays(nums1, nums2));//输出：2.50000
        System.out.println("测试三");
        nums1 = new int[]{0, 0};
        nums2 = new int[]{0, 0};
        System.out.println(findMedianSortedArrays(nums1, nums2));//输出：0.00000
        System.out.println("测试四");
        nums1 = new int[]{};
        nums2 = new int[]{1};
        System.out.println(findMedianSortedArrays(nums1, nums2));//输出：1.00000
        System.out.println("测试五");
        nums1 = new int[]{2};
        nums2 = new int[]{};
        System.out.println(findMedianSortedArrays(nums1, nums2));//输出：2.00000
    }

    /**
     * @Author jatej
     * @Description 方案一：将两个集合组合成一个大的有序集合
     **/
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<Integer>(nums1.length + nums2.length);
        for (int num : nums1) {
            list.add(num);
        }
        for (int num : nums2) {
            list.add(num);
        }
        Collections.sort(list);
        System.out.println("当前集合为" + list);
        if (list.size() % 2 == 1) {
            return (double) list.get(list.size() / 2);
        }
        return (list.get(list.size() / 2) + list.get(list.size() / 2 - 1)) / 2.0;
    }

    /**
     * @Author jatej
     * @Description 方案二：采用下标的方式(待定)
     **/
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
       int length1 = nums1.length;
       int length2 = nums2.length;
       int totalLength = length1 + length2;
       if( totalLength %2 == 1 ){
           int midIndex = totalLength / 2;
       }
       return 0;
    }

    //获取第k个位置的元素
    private static double getKthElement(int[] nums1,int[] nums2,int k){
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */
        return  0;
    }


}
